\documentclass{ctexart}
\usepackage{graphicx}
\usepackage{listings}
\usepackage{color}

\pagestyle{headings}

\title{Graph设计思路和测试说明}
\author{谢飞扬 \\ 信息与计算科学 3210104010}
\date{\today}

\definecolor{green}{rgb}{0,0.7,0}
\definecolor{blue}{rgb}{0,0,0.8}
\definecolor{gray}{rgb}{0.95,0.95,0.95}
\definecolor{red}{rgb}{0.6,0,0}

\lstset{
        language=C++,
	basicstyle=\small\ttfamily,	
		keywordstyle=\color{blue}, 
		commentstyle=\color{green},   
		stringstyle=\rmfamily\slshape\color{red}, 
	backgroundcolor=\color{gray},     % 代码块背景颜色
	frame=leftline,						% 代码框形状
	framerule=12pt,
	rulecolor=\color{gray},      % 代码框颜色
	numbers=left,				% 左侧显示行号往左靠, 还可以为right ，或none，即不加行号
		numberstyle=\footnotesize\itshape,	% 行号的样式
		firstnumber=1,
		stepnumber=1,                  	% 若设置为2，则显示行号为1,3,5
		numbersep=5pt,               	% 行号与代码之间的间距
	keepspaces=true, 					
	showtabs=false,                 	% 在字符串中显示制表符
	tabsize=2,                     		% 默认缩进2个字符
	captionpos=b,                   	% 将标题位置设置为底部
	flexiblecolumns=true, 			%
	breaklines=true,                	% 设置自动断行
	breakatwhitespace=false,        	% 设置自动中断是否只发生在空格处
	breakautoindent=true,			%
	breakindent=1em, 			%
	title=\lstname,				%
	xleftmargin=1em,  xrightmargin=0em,     % 设定listing左右的空白
	aboveskip=1ex, belowskip=1ex,
	framextopmargin=0.5pt, framexbottommargin=0.5pt,
        abovecaptionskip=-2pt,belowcaptionskip=3pt,
	% 设定中文冲突，断行，列模式，数学环境输入，listing数字的样式
	extendedchars=false, columns=flexible, mathescape=true,
	texcl=true,
        fontadjust
}

\begin{document}
\maketitle
\section{项目设计思路}
\subsection{类的封装和继承关系}
Graph类是基类，DGraph和UdGraph则是其派生类，Vertex和Edge也都封装成模版类，顶点中可以存放各类数据。Graph作为抽象类，设计了插入顶点、删除顶点、插入边、删除边，四个纯虚函数。两个派生类则根据作业要求增加了打印顶点和边的函数，同时还增加了函数判断顶点和边是否存在。对于题目要求的两种存储方式，邻接表我将其作为顶点的成员属性方便维护，而邻接矩阵则作为图的成员属性，顶点也以数组的形式作为图的成员属性。另外我用了STL库的vector和list，方便管理图中的顶点和边。
\subsection{作业要求的具体实现}
首先是图的存储方式的选择，我在图中增加了成员属性记录存储方式，所有成员函数都根据用户输入的存储模式选择邻接表或是邻接矩阵的对应代码，直接初始化图时则默认选择邻接表存储。用户没有指定存储模式时，图根据用户输出的图可能的最大顶点数和最大边数来决定存储模式。当边数接近顶点数的平方时，用邻接矩阵存储，否则，用邻接表存储。
\\其次是列出全部节点和边的成员函数实现，下面给出代码。
\begin{lstlisting}
    void listVertexes()const
    {
	for(typename vector<Vertex<T>>::const_iterator itr=VertexTable.begin();itr!=VertexTable.end();++itr)
	    cout<<(*itr).data<<" ";
	cout<<endl;
	return;
    }
    void listEdges()const
    {
	if(storagemode==0)
	{
	    for(typename vector<Vertex<T>>::const_iterator itr1=VertexTable.begin();itr1!=VertexTable.end();++itr1)
	    {
		for(typename list<Edge<T>>::const_iterator itr2=(*itr1).adj.begin();itr2!=(*itr1).adj.end();++itr2)
		    cout<<"("<<(*(*itr2).from).data<<","<<(*(*itr2).to).data<<","<<(*itr2).weight<<") ";
	    }
	    cout<<endl;
	    return;
	}
	else
	{
	    for(int i=0;i<numVertex;i++)
		for(int j=0;j<numVertex;j++)
		    if(EdgeMatrix[i][j])
			cout<<"("<<VertexTable[i].data<<","<<VertexTable[j].data<<","<<EdgeMatrix[i][j]<<") ";
	    cout<<endl;
	    return;
	}
    }
\end{lstlisting}
\section{测试说明}
在main函数中调用了四个测试函数，分别测试了邻接矩阵无向图、邻接表无向图、邻接矩阵有向图、邻接表有向图的所有函数，及函数的各种异常情况和极端情况。经反复调试和改进基本无BUG，经测试无内存泄漏。
\end{document}
